/**
 * RVO 四叉树优化版本
 * 
 * @description
 * 使用优化版四叉树替代 KD-Tree 进行邻居搜索
 * 
 * 性能优势：
 * 1. 增量更新 - KD-Tree 每帧完全重建，四叉树支持增量更新
 * 2. 对象池 - 减少 GC 压力
 * 3. 查询缓存 - 相同位置的重复查询可以缓存
 * 4. 更简单的构建 - O(n log n) vs KD-Tree 的分区排序
 * 
 * @packageDocumentation
 */

import { QuadtreeOptimized } from '../quadtree/QuadtreeOptimized';
import { Rectangle } from '../quadtree/Rectangle';
import { Agent } from './Agent';
import { Obstacle, Vector2, KeyValuePair, RVOMath } from './Common';
import { Simulator } from './Simulator';
import { Log } from '../logger/LoggerGlobal';

/**
 * RVO 代理包装类（用于四叉树）
 */
class RVOAgentWrapper extends Rectangle<Agent> {
    constructor(agent: Agent) {
        const pos = agent.position_;
        const radius = agent.radius_;
        
        super({
            x: pos.x - radius,
            y: pos.y - radius,
            width: radius * 2,
            height: radius * 2,
            data: agent
        });
    }
    
    /**
     * 更新包装器位置
     */
    updatePosition(): void {
        const agent = this.data!;
        const pos = agent.position_;
        const radius = agent.radius_;
        
        this.x = pos.x - radius;
        this.y = pos.y - radius;
        this.width = radius * 2;
        this.height = radius * 2;
    }
}

/**
 * 基于四叉树的 RVO 空间索引
 * 
 * 相比 KD-Tree 的优势：
 * 1. 支持增量更新（不需要每帧重建）
 * 2. 更简单的数据结构
 * 3. 更好的缓存友好性
 * 4. 支持对象池减少 GC
 */
export class RVOQuadtree {
    
    /** 代理四叉树 */
    private agentTree: QuadtreeOptimized<RVOAgentWrapper> | null = null;
    
    /** 障碍物四叉树 */
    private obstacleTree: QuadtreeOptimized<Rectangle<Obstacle>> | null = null;
    
    /** 代理包装器映射 */
    private agentWrappers: Map<number, RVOAgentWrapper> = new Map();
    
    /** 世界边界 */
    private worldBounds = {
        width: 2000,
        height: 2000,
        x: -1000,
        y: -1000
    };
    
    /** 统计信息 */
    private stats = {
        agentQueries: 0,
        obstacleQueries: 0,
        cacheHits: 0,
        buildTime: 0,
        queryTime: 0
    };
    
    /** 是否启用增量更新 */
    private enableIncrementalUpdate: boolean = true;
    
    constructor(
        worldWidth: number = 2000,
        worldHeight: number = 2000,
        worldX: number = -1000,
        worldY: number = -1000
    ) {
        this.worldBounds = { width: worldWidth, height: worldHeight, x: worldX, y: worldY };
        
        // 创建代理四叉树
        this.agentTree = new QuadtreeOptimized<RVOAgentWrapper>({
            ...this.worldBounds,
            maxObjects: 10,
            maxLevels: 5,
            enableObjectPool: true,
            enableQueryCache: true,
            enableIncrementalUpdate: true
        });
        
        // 创建障碍物四叉树
        this.obstacleTree = new QuadtreeOptimized<Rectangle<Obstacle>>({
            ...this.worldBounds,
            maxObjects: 10,
            maxLevels: 5,
            enableObjectPool: true,
            enableQueryCache: true,
            enableIncrementalUpdate: false  // 障碍物通常是静态的
        });
        
        Log.ecs.info('RVOQuadtree 已创建', {
            世界大小: `${worldWidth}x${worldHeight}`,
            世界偏移: `(${worldX}, ${worldY})`
        });
    }
    
    /**
     * 构建代理树（增量更新模式）
     */
    buildAgentTree(agentNum: number): void {
        if (!this.agentTree) return;
        
        const startTime = performance.now();
        
        const sim = Simulator.instance;
        
        if (this.enableIncrementalUpdate) {
            // 增量更新模式 - 只更新移动的代理
            
            // 1. 检查是否有新增/删除的代理
            const currentAgentIds = new Set<number>();
            for (let i = 0; i < agentNum; i++) {
                const agent = sim.getAgent(i);
                currentAgentIds.add(agent.id);
                
                let wrapper = this.agentWrappers.get(agent.id);
                
                if (!wrapper) {
                    // 新代理，创建包装器
                    wrapper = new RVOAgentWrapper(agent);
                    this.agentWrappers.set(agent.id, wrapper);
                    this.agentTree.insert(wrapper);
                } else {
                    // 已存在的代理，更新位置
                    wrapper.updatePosition();
                    this.agentTree.update(wrapper);
                }
            }
            
            // 2. 移除不再存在的代理
            for (const [agentId, wrapper] of this.agentWrappers) {
                if (!currentAgentIds.has(agentId)) {
                    this.agentTree.remove(wrapper);
                    this.agentWrappers.delete(agentId);
                }
            }
            
        } else {
            // 完全重建模式（兼容 KD-Tree 行为）
            this.agentTree.clear();
            this.agentWrappers.clear();
            
            for (let i = 0; i < agentNum; i++) {
                const agent = sim.getAgent(i);
                const wrapper = new RVOAgentWrapper(agent);
                this.agentWrappers.set(agent.id, wrapper);
                this.agentTree.insert(wrapper);
            }
        }
        
        this.stats.buildTime = performance.now() - startTime;
    }
    
    /**
     * 构建障碍物树
     */
    buildObstacleTree(): void {
        if (!this.obstacleTree) return;
        
        this.obstacleTree.clear();
        
        const sim = Simulator.instance;
        const obstacles = sim.obstacles;
        
        for (const obstacle of obstacles) {
            // 将障碍物线段转换为矩形
            if (!obstacle.next) continue;
            
            const p1 = obstacle.point;
            const p2 = obstacle.next.point;
            
            const minX = Math.min(p1.x, p2.x);
            const minY = Math.min(p1.y, p2.y);
            const maxX = Math.max(p1.x, p2.x);
            const maxY = Math.max(p1.y, p2.y);
            
            // 为线段创建包围盒（加上一定的余量）
            const margin = 1.0;
            const rect = new Rectangle<Obstacle>({
                x: minX - margin,
                y: minY - margin,
                width: (maxX - minX) + margin * 2,
                height: (maxY - minY) + margin * 2,
                data: obstacle
            });
            
            this.obstacleTree.insert(rect);
        }
        
        Log.ecs.info('障碍物树已构建', {
            障碍物数量: obstacles.length
        });
    }
    
    /**
     * 计算代理邻居（使用四叉树）
     */
    computeAgentNeighbors(agent: Agent, rangeSq: number): number {
        if (!this.agentTree) return rangeSq;
        
        const startTime = performance.now();
        this.stats.agentQueries++;
        
        const range = Math.sqrt(rangeSq);
        const pos = agent.position_;
        
        // 使用圆形查询
        const candidates = this.agentTree.queryCircle(pos.x, pos.y, range);
        
        // 过滤并排序邻居
        const neighbors: KeyValuePair<number, Agent>[] = [];
        
        for (const wrapper of candidates) {
            const other = wrapper.data!;
            
            // 跳过自己
            if (other.id === agent.id) continue;
            
            // 计算距离平方
            const distSq = pos.minus(other.position_).lengthSqr();
            
            // 在范围内
            if (distSq < rangeSq) {
                neighbors.push(new KeyValuePair(distSq, other));
            }
        }
        
        // 按距离排序
        neighbors.sort((a, b) => a.key - b.key);
        
        // 限制邻居数量
        if (neighbors.length > agent.maxNeighbors_) {
            neighbors.length = agent.maxNeighbors_;
            rangeSq = neighbors[neighbors.length - 1].key;
        }
        
        // 添加到代理的邻居列表
        agent.agentNeighbors_.length = 0;
        agent.agentNeighbors_.push(...neighbors);
        
        this.stats.queryTime += performance.now() - startTime;
        
        return rangeSq;
    }
    
    /**
     * 计算障碍物邻居（使用四叉树）
     */
    computeObstacleNeighbors(agent: Agent, rangeSq: number): void {
        if (!this.obstacleTree) return;
        
        this.stats.obstacleQueries++;
        
        const range = Math.sqrt(rangeSq);
        const pos = agent.position_;
        
        // 使用圆形查询
        const candidates = this.obstacleTree.queryCircle(pos.x, pos.y, range);
        
        // 过滤障碍物
        const neighbors: KeyValuePair<number, Obstacle>[] = [];
        
        for (const rect of candidates) {
            const obstacle = rect.data!;
            if (!obstacle.next) continue;
            
            // 计算点到线段的距离
            const distSq = RVOMath.distSqPointLineSegment(
                obstacle.point,
                obstacle.next.point,
                pos
            );
            
            if (distSq < rangeSq) {
                neighbors.push(new KeyValuePair(distSq, obstacle));
            }
        }
        
        // 按距离排序
        neighbors.sort((a, b) => a.key - b.key);
        
        // 添加到代理的障碍物邻居列表
        agent.obstaclNeighbors_.length = 0;
        agent.obstaclNeighbors_.push(...neighbors);
    }
    
    /**
     * 查询可见性（射线检测）
     */
    queryVisibility(q1: Vector2, q2: Vector2, radius: number): boolean {
        if (!this.obstacleTree) return true;
        
        // 创建查询区域（线段的包围盒）
        const minX = Math.min(q1.x, q2.x) - radius;
        const minY = Math.min(q1.y, q2.y) - radius;
        const maxX = Math.max(q1.x, q2.x) + radius;
        const maxY = Math.max(q1.y, q2.y) + radius;
        
        const candidates = this.obstacleTree.queryRect(
            minX,
            minY,
            maxX - minX,
            maxY - minY
        );
        
        // 检查与障碍物的相交
        for (const rect of candidates) {
            const obstacle = rect.data!;
            if (!obstacle.next) continue;
            
            // 检查线段相交
            if (this.lineSegmentIntersect(q1, q2, obstacle.point, obstacle.next.point, radius)) {
                return false;
            }
        }
        
        return true;
    }
    
    /**
     * 线段相交检测
     */
    private lineSegmentIntersect(
        p1: Vector2,
        p2: Vector2,
        p3: Vector2,
        p4: Vector2,
        radius: number
    ): boolean {
        // 简化实现：检查点到线段的距离
        const distSq1 = RVOMath.distSqPointLineSegment(p3, p4, p1);
        const distSq2 = RVOMath.distSqPointLineSegment(p3, p4, p2);
        const radiusSq = radius * radius;
        
        return distSq1 < radiusSq || distSq2 < radiusSq;
    }
    
    /**
     * 获取统计信息
     */
    getStats() {
        const agentTreeStats = this.agentTree?.getStats() || {};
        const obstacleTreeStats = this.obstacleTree?.getStats() || {};
        
        return {
            ...this.stats,
            代理树: agentTreeStats,
            障碍物树: obstacleTreeStats,
            代理包装器数量: this.agentWrappers.size
        };
    }
    
    /**
     * 重置统计信息
     */
    resetStats(): void {
        this.stats = {
            agentQueries: 0,
            obstacleQueries: 0,
            cacheHits: 0,
            buildTime: 0,
            queryTime: 0
        };
        
        this.agentTree?.resetStats();
        this.obstacleTree?.resetStats();
    }
    
    /**
     * 打印统计信息
     */
    printStats(): void {
        const stats = this.getStats();
        
        Log.styled('━'.repeat(60), 'separator');
        Log.styled('📊 RVOQuadtree 统计', 'title');
        Log.styled('━'.repeat(60), 'separator');
        
        Log.performance.info('查询统计', {
            代理查询: stats.agentQueries,
            障碍物查询: stats.obstacleQueries,
            构建耗时: `${stats.buildTime.toFixed(2)}ms`,
            查询耗时: `${stats.queryTime.toFixed(2)}ms`
        });
        
        Log.performance.info('四叉树统计', {
            代理包装器: stats.代理包装器数量,
            代理树缓存命中率: (stats.代理树 as any).cacheHitRate || 0,
            障碍物树缓存命中率: (stats.障碍物树 as any).cacheHitRate || 0
        });
        
        Log.styled('━'.repeat(60), 'separator');
    }
    
    /**
     * 设置增量更新模式
     */
    setIncrementalUpdate(enabled: boolean): void {
        this.enableIncrementalUpdate = enabled;
        Log.ecs.info(`增量更新模式: ${enabled ? '启用' : '禁用'}`);
    }
    
    /**
     * 清理
     */
    destroy(): void {
        this.agentTree?.destroy();
        this.obstacleTree?.destroy();
        this.agentWrappers.clear();
        
        Log.ecs.info('RVOQuadtree 已销毁');
    }
}

